package com.ls.que96_100;

import com.ls.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ：ls
 * @date ：2022/3/12 10:32
 * @description：...
 */
public class NumTrees {
    public static int numTrees(int n) {
        if (n==1)
            return 0;
        return gen(1,n);
    }

    public static int gen(int start, int end){
        if (start > end){
            return 1;
        }
        int sum = 0;
        for (int i=start; i<=end; i++){
            int l = gen(start, i-1);
            int r = gen(i+1, end);
            sum += l*r;
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(numTrees(19));
    }
}
